
/*-------------------------------------------------------------------------
 *
 * pg_bitutils.c
 *	  位运算的杂项函数。
 *
 * Copyright (c) 2019-2022, PostgreSQL Global Development Group
 *
 * IDENTIFICATION
 *	  src/port/pg_bitutils.c
 *
 *-------------------------------------------------------------------------
 */
#include "c.h"

#ifdef HAVE__GET_CPUID
#include <cpuid.h>
#endif
#ifdef HAVE__CPUID
#include <intrin.h>
#endif

#include "port/pg_bitutils.h"


/*
 * 数组给出每个可能字节值的最左边设置位的位置。我们将最右边的位置计为第0位，最左边计为第7位。数组的第0个条目不应使用。
 *
 * 注意：当定义了HAVE__BUILTIN_CLZ时，pg_bitutils.h中的函数不使用此项，但我们仍提供它，以便可能用不同编译器编译的扩展可以使用它。
 */
const uint8 pg_leftmost_one_pos[256] = {
	0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
	4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
	5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
	5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
	6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
	6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
	6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
	6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
};

/*
 * 数组给出每个可能字节值的最右边设置位的位置。我们将最右边的位置计为第0位，最左边计为第7位。数组的第0个条目不应使用。
 *
 * 注意：当定义了HAVE__BUILTIN_CTZ时，pg_bitutils.h中的函数不使用此项，但我们仍提供它，以便可能用不同编译器编译的扩展可以使用它。
 */
const uint8 pg_rightmost_one_pos[256] = {
	0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
};

/*
 * 数组给出每个可能字节值中1位的数量。
 *
 * 注意：我们导出此项供函数使用，其中明确使用popcount函数似乎不太可能带来收益。
 */
const uint8 pg_number_of_ones[256] = {
	0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};

static int	fc_pg_popcount32_slow(uint32 fc_word);
static int	fc_pg_popcount64_slow(uint64 fc_word);

#ifdef TRY_POPCNT_FAST
static bool fc_pg_popcount_available(void);
static int	fc_pg_popcount32_choose(uint32 fc_word);
static int	fc_pg_popcount64_choose(uint64 fc_word);
static int	fc_pg_popcount32_fast(uint32 fc_word);
static int	fc_pg_popcount64_fast(uint64 fc_word);

int			(*pg_popcount32) (uint32 word) = fc_pg_popcount32_choose;
int			(*pg_popcount64) (uint64 word) = fc_pg_popcount64_choose;
#endif							/* 尝试快速POPcnt */

#ifdef TRY_POPCNT_FAST

/*
 * 如果CPUID指示可以使用POPCNT指令，则返回true。
 */
static bool fc_pg_popcount_available(void)
{
	unsigned int fc_exx[4] = {0, 0, 0, 0};

#if defined(HAVE__GET_CPUID)
	__get_cpuid(1, &fc_exx[0], &fc_exx[1], &fc_exx[2], &fc_exx[3]);
#elif defined(HAVE__CPUID)
	__cpuid(fc_exx, 1);
#else
#error cpuid instruction not available
#endif

	return (fc_exx[2] & (1 << 23)) != 0;	/* POPCNT */
}

/*
 * 这些函数在首次调用pg_popcount32等时被调用。
 * 它们检测我们是否可以使用asm实现，并替换函数指针，以便后续调用直接路由到所选实现。
 */
static int fc_pg_popcount32_choose(uint32 fc_word)
{
	if (fc_pg_popcount_available())
	{
		pg_popcount32 = fc_pg_popcount32_fast;
		pg_popcount64 = fc_pg_popcount64_fast;
	}
	else
	{
		pg_popcount32 = fc_pg_popcount32_slow;
		pg_popcount64 = fc_pg_popcount64_slow;
	}

	return pg_popcount32(fc_word);
}

static int fc_pg_popcount64_choose(uint64 fc_word)
{
	if (fc_pg_popcount_available())
	{
		pg_popcount32 = fc_pg_popcount32_fast;
		pg_popcount64 = fc_pg_popcount64_fast;
	}
	else
	{
		pg_popcount32 = fc_pg_popcount32_slow;
		pg_popcount64 = fc_pg_popcount64_slow;
	}

	return pg_popcount64(fc_word);
}

/*
 * pg_popcount32_fast
 *		返回字中设置的1位数量
 */
static int fc_pg_popcount32_fast(uint32 fc_word)
{
#ifdef _MSC_VER
	return __popcnt(fc_word);
#else
	uint32		fc_res;

__asm__ __volatile__(" popcntl %1,%0\n":"=q"(fc_res):"rm"(fc_word):"cc");
	return (int) fc_res;
#endif
}

/*
 * pg_popcount64_fast
 *		返回字中设置的1位数量
 */
static int fc_pg_popcount64_fast(uint64 fc_word)
{
#ifdef _MSC_VER
	return __popcnt64(fc_word);
#else
	uint64		fc_res;

__asm__ __volatile__(" popcntq %1,%0\n":"=q"(fc_res):"rm"(fc_word):"cc");
	return (int) fc_res;
#endif
}

#endif							/* 尝试快速POPcnt */


/*
 * pg_popcount32_slow
 *		返回字中设置的1位数量
 */
static int fc_pg_popcount32_slow(uint32 fc_word)
{
#ifdef HAVE__BUILTIN_POPCOUNT
	return __builtin_popcount(fc_word);
#else							/* !HAVE__BUILTIN_POPCOUNT */
	int			fc_result = 0;

	while (fc_word != 0)
	{
		fc_result += pg_number_of_ones[fc_word & 255];
		fc_word >>= 8;
	}

	return fc_result;
#endif							/* HAVE__BUILTIN_POPCOUNT */
}

/*
 * pg_popcount64_slow
 *		返回字中设置的1位数量
 */
static int fc_pg_popcount64_slow(uint64 fc_word)
{
#ifdef HAVE__BUILTIN_POPCOUNT
#if defined(HAVE_LONG_INT_64)
	return __builtin_popcountl(fc_word);
#elif defined(HAVE_LONG_LONG_INT_64)
	return __builtin_popcountll(fc_word);
#else
#error must have a working 64-bit integer datatype
#endif
#else							/* !HAVE__BUILTIN_POPCOUNT */
	int			fc_result = 0;

	while (fc_word != 0)
	{
		fc_result += pg_number_of_ones[fc_word & 255];
		fc_word >>= 8;
	}

	return fc_result;
#endif							/* HAVE__BUILTIN_POPCOUNT */
}

#ifndef TRY_POPCNT_FAST

/*
 * 当POPCNT指令不可用时，使用函数指针在快速和慢速方法之间变更实现是没有意义的。
 * 我们仅在未定义TRY_POPCNT_FAST时将这些实际变为外部函数。
 * 编译器应能够在这里内联慢版本。
 */
int pg_popcount32(uint32 word)
{
	return pg_popcount32_slow(word);
}

int pg_popcount64(uint64 word)
{
	return pg_popcount64_slow(word);
}

#endif							/* !尝试快速POPcnt */

/*
 * pg_popcount
 *		返回buf中1位的数量
 */
uint64 pg_popcount(const char *fc_buf, int fc_bytes)
{
	uint64		fc_popcnt = 0;

#if SIZEOF_VOID_P >= 8
	/* 如果缓冲区对齐，则以64位块处理。 */
	if (fc_buf == (const char *) TYPEALIGN(8, fc_buf))
	{
		const uint64 *fc_words = (const uint64 *) fc_buf;

		while (fc_bytes >= 8)
		{
			fc_popcnt += pg_popcount64(*fc_words++);
			fc_bytes -= 8;
		}

		fc_buf = (const char *) fc_words;
	}
#else
	/* 如果缓冲区对齐，则以32位块处理。 */
	if (buf == (const char *) TYPEALIGN(4, buf))
	{
		const uint32 *words = (const uint32 *) buf;

		while (bytes >= 4)
		{
			popcnt += pg_popcount32(*words++);
			bytes -= 4;
		}

		buf = (const char *) words;
	}
#endif

	/* 处理任何剩余字节 */
	while (fc_bytes--)
		fc_popcnt += pg_number_of_ones[(unsigned char) *fc_buf++];

	return fc_popcnt;
}
